\chapter{Object system}

\sysname{} will implement the full metaobject protocol (MOP) as
described by the Art of the Metaobject Protocol (AMOP)
\cite{Kiczales:1991:AMP:574212}, in as far it does not conflict with
the standard.

\section{Classes of class metaobjects}

The AMOP stipulates the existence of four class metaclasses, namely:

\begin{itemize}
\item \href{http://www.metamodular.com/CLOS-MOP/class-standard-class.html}
  {\texttt{standard-class}}.
  This is the default metaclass for classes
  created by \texttt{defclass}.  It is also the metaclass for all
  classes in the metaobject protocol except \texttt{t},
  \texttt{function}, \texttt{generic-function}, and
  \texttt{standard-generic\-function}.
\item \href{http://www.metamodular.com/CLOS-MOP/class-funcallable-standard-class.html}
{\texttt{funcallable-standard-class}}.
This is the metaclass for
\texttt{funcallable\-standard-object},
and of course for subclasses of that class such as
\texttt{generic-function},
and
\texttt{standard-generic-function},
\item \href{http://www.metamodular.com/CLOS-MOP/class-built-in-class.html}
{\texttt{built-in-class}}.  
This is the metaclass for all built-in
classes.  More about built-in classes in
\refSec{object-system-built-in-classes}. 
\item \href{http://www.metamodular.com/CLOS-MOP/class-forward-referenced-class.html}
{\texttt{forward-referenced-class}}.  This is the metaclass for
  classes that have been referred to as superclasses, but that have
  not yet been created by \texttt{defclass}.
\end{itemize}

In addition, the standard requires the existence of a class metaclass
named \texttt{structure-class}.  Whether conditions have their own
metaclass is not specified.  \sysname{} defines the class
\texttt{condition-class} for this purpose.

In \sysname{}, every class (i.e., every instance of a metaclass)
contains a \emph{unique number} which is an integer assigned
sequentially from $0$ as a class is created or modified.  When a class
is modified, its old unique number is never reused, leaving
\emph{holes} in the sequence corresponding to numbers that no longer
correspond to any classes.%
\footnote{It might be possible for the garbage collector to change the
  unique numbers of the classes, compacting the sequence, but that
  probably will not be necessary.}

Every \emph{standard object}%
\footnote{Recall that a \emph{standard object} is an instance
  allocated on the heap, excluding \texttt{cons}
  cells. \seechap{chap-data-representation}} contains a \emph{stamp},
which is the unique number of its class as it was when the instance
was created.  This number is always the first element of the rack of
the standard-object.  Even though some system classes can not be
redefined, standard objects that are instance of system classes
contain a stamp.

\subsection{Standard classes}
\label{object-system-standard-classes}

Instances of \texttt{standard-class} (i.e. ``standard classes'') are
typically created by \texttt{defclass}.  When no superclasses are
given to \texttt{defclass}, the class \texttt{standard-object} is
automatically made a superclass of the new class.  

Perhaps the most interesting feature of standard classes is that they
can be redefined even though there are existing instances of them.
Without this feature, using \commonlisp{} interactively would not be as
obvious as it is, so in some ways, this feature is totally essential
for any interactive language.%
\footnote{By ``interactive language'', we mean a language in which a
  program is built up by a sequence of interactions that augment and
  modify the state of some \emph{global environment}.}

When there are existing instances of a standard class that is
modified, the standard gives us very specific rules concerning how
those instances are to be updated.  The standard is also very clear
that existing instances do not need to be updated immediately.  But
they must be updated no later than immediately before an access to any
of the slots of the instance is attempted.   The reason for that rule
is so that implementations would not have to maintain a reference from
a class to each of its instance.  Such references would be costly in
terms of space, and would have to be \emph{weak}%
\footnote{A \emph{weak} reference is a reference that is not
  sufficient for the garbage collector to keep the object alive.  The
  object is kept alive only if there is at least one \emph{strong}
  (i.e. normal) reference to it as well.}  so as to avoid memory
leaks.

Instead of keeping weak references from classes to instances,
implementations solve the problem of updating obsolete instance by
keeping some kind of \emph{version information} in each instance.
When some operation on the instance is attempted, the version
information is checked against the current version of the class.  If
the instance is obsolete, it is first updated according to the new
definition of the class.  Furthermore, the version information must
contain enough information of the class as it was when the instance
was created to determine whether slots have been added or removed.

In \sysname{} the first location of the rack of each standard-object
contains a \emph{stamp}, which is the unique number of the class as it
was when the instance was created.  In addition, it contains a
reference to the \emph{list of effective slots} of the class as it was
when the instance was created.  This technique makes the rack of the
instance completely self contained.  It allows the garbage collector
to trace the obsolete instance, or update it before tracing.  It
allows for an inspector to inspect the obsolete instance if this
should be required.  The main purpose of the list of effective slots,
however, is making it possible to update an obsolete instance.

Another very handy feature of standard classes, but a much simpler
one, is that it allows for instances to \emph{change class}.  In other
words, without changing the \emph{identity} of the instance, the class
that it is an instance of can be changed to a different class.  Again,
the standard gives very specific rules about how the instance must be
transformed in order to be a legitimate instance of the new class.  No
special mechanism is required for this feature to work, other than the
ability to modify all aspects of an instance except its identity.  The
identity is preserved by the fact that the \emph{header object}
remains the same. 

\subsection{Built-in classes}
\label{object-system-built-in-classes}

The standard contains a significant number of classes that every
conforming implementation must contain.  Most (all?) of these classes
are referred to as \emph{system classes}.  Some example of system
classes are \texttt{symbol}, \texttt{package}, \texttt{list},
\texttt{stream}, etc.  The standard tells us that by \emph{system
  class} is meant ``a class that may be of type built-in-class in a
conforming implementation and hence cannot be inherited by classes
defined by conforming programs.'' 

Language implementers are thus given a choice as to whether a system
class is really a standard class
\seesec{object-system-standard-classes}, a structure class 
\seesec{object-system-structure-classes}, or a built-in class.

Some of the decisions are determined by the AMOP.  For instance, the
classes \texttt{standard-class} and \texttt{built-in-class}, labeled
by the standard as system classes are required by the AMOP to be
standard classes.  Any implementation that wants to have an
implementation of the metaobject protocol as close as possible to what
the AMOP requires should take this fact into account. 

However, most system classes are not mentioned at all by the AMOP, so
there we have a choice.  In \sysname{} all these classes will be
implemented as either built-in classes or standard classes.  None of
them will be structure classes. 

Even though \sysname{} will implement some of the system classes as
built-in classes, this does not mean that we have to use
special-purpose ways of implementing them.  The \sysname{} object
system takes advantage of features of the metaobject protocol such as
inheritance to define built-in classes as well as standard classes.

Even for system classes where instances do not all have the same size,
notably the \texttt{array} class and its subclasses, we plan to take
advantage of the metaobject protocol by allowing
\texttt{make-instance} to take a \emph{size} argument in addition to
ordinary initialization arguments.  We also plan to allow
\texttt{defclass} to define built-in classes by passing it
\texttt{built-in-class} as a metaclass.  In that case, the default
superclass is \texttt{t} instead of \texttt{standard-object}.  This
technique allows us to concentrate all important features of a
built-in class and its instances in one place, which will simplify
maintenance.

\subsection{Condition classes}
\label{object-system-condition-classes}

The standard defines an entire hierarchy of classes with the class
\texttt{condition} as the root class.  This hierarchy is not mentioned
by the AMOP.  

We plan to implement this hierarchy by defining a class named
\texttt{condition-class} analogous to \texttt{standard-class} for
standard objects.  The class \texttt{condition} plays a role analogous
to the class \texttt{standard-object} for instances of
\texttt{standard-class}. 

As with built-in classes \seesec{object-system-built-in-classes}, we
plan to take advantage of the very complete set of tools provided by
the metaobject protocol to implement condition classes.  In
particular, we want to allow for condition classes to be redefined
even though existing instances may be present, just the way instances
of \texttt{standard-object} may exist even though the class is being
modified.  However, we do not plan to make it possible for an instance
of a condition class to have its class changed (i.e. by using
\texttt{change-class}).  

With respect to bootstrapping, the hierarchy of condition classes can
be created fairly late in the process.  The reason for this is that we
plan to define a dumbed-down version of \texttt{error} during the
bootstrapping process, and that version will not create any condition
instances.  Furthermore, all \sysname{} code calls \texttt{error} and
the other condition-signaling functions with the \emph{name} of a
condition (which is a symbol) rather than with a \emph{condition
  instance}, again to allow us to create this hierarchy later in the
bootstrapping process. 

\subsection{Structure classes}
\label{object-system-structure-classes}

Just like condition classes \seesec{object-system-condition-classes},
structure classes are not mentioned at all in the AMOP.  In addition,
their description in the standard is limited to the dictionary entry
for \texttt{defstruct}.  

No part of \sysname{} uses structure classes.  The main reason is that
they are difficult to work with due to the fact that conforming
implementations are allowed to make it impossible to redefine
existing structure classes.%
\footnote{I seem to remember reading somewhere that implementers are
  encouraged to make it possible to modify existing structure classes
  in the same way that it is possible to modify standard classes even
  though there are existing instances, but I don't remember where I
  read this, and I can't seem to find the place.  It might have been
  in CLtL2 rather than the standard, but I can't find it there
  either.  Oh well, when I find it, I will remove this footnote.}

However, since we plan for \sysname{} to be a conforming
implementation, we naturally plan to include structure classes as
well. 

The main reason for using structure classes rather than standard
classes is \emph{performance}.  Structure classes are supposed to be
implemented in the ``most efficient way possible''.%
\footnote{Again, I forget where I read this, and I can't find it.}
Presumably, the restrictions on structure classes exist to allow for
an implementation to represent instances as a pointer directly to the
vector of slots and avoid any indirection, which saves some memory
accesses%
\footnote{No checks for outdatedness, etc.}
However, in \sysname{} \emph{all} heap-allocated objects
(other than \texttt{cons} cells) are represented as a two-word
\emph{header object} and a \emph{rack} for reasons of
simplicity and in order to allow our memory-management strategy to
work.

Since \sysname{} represents instances of structure classes this way,
there is no reason to keep the restriction that structure classes can
not be modified.  For that reason, we plan to avoid that restriction.

Structure classes have another interesting restriction, namely that
they allow only single inheritance.  This restriction allows slot
accessors to be non-generic, because it becomes possible for a slot to
have the same physical position in all subclasses.  We may or may not
take advantage of this possibility.  The higher priority for
\sysname{} is to make accessors for standard objects fast, rather than
to work on an efficient implementation of structures. 

With respect to bootstrapping, since \sysname{} does not use structure
classes at all for its implementation, implementing \texttt{defstruct}
can be done fairly late.  In fact, we may omit it in the initial version
of the system. 

\section{Generic function dispatch}
\label{sec-generic-function-dispatch}

We use the generic dispatch algorithm described in our paper at ICL
2014 \cite{Strandh:2014:FGD:2635648.2635654}

The documentation of generic dispatch has moved to Clostrophilia.

\section{Dealing with metastability issues}
\label{sec-object-system-dealing-with-metastability-issues}

The AMOP gives a few examples of metastability issues that need to be
dealt with.  It also suggests solutions to these problems, based on
recognizing \emph{special cases} such as when \texttt{class-slots} is
called with the class named \texttt{standard-class}.  

In \sysname{} we use a different method, called \emph{satiation}.
Satiation, in effect, turns metastability problems into
\emph{bootstrapping problems} which are much easier to deal with.
This technique is documented in our paper at ILC 2014
\cite{Strandh:2014:RMI:2635648.2635656}.

\begin{definition}
A generic function $F$ is said to be \emph{satiated} with respect to a
set of classes $C$ if and only if for every combination of classes of
required arguments of $F$ for which an effective method can be
computed, if a call is made to $F$ with such a combination, then an
effective method exists in the cache of $F$ so that no additional
generic function needs to be invoked in order for the corresponding
effective method to be called.
\end{definition}

As part of bootstrapping the object system, every specified%
\footnote{By the AMOP.} generic function is satiated with respect to
the set of specified classes.  Furthermore, since specified classes
can not be redefined, we can make sure that every specified generic
function always remains satiated with respect to the set of specified
classes.

\begin{theorem}
If every specified generic function is satiated with respect to the
set of specified classes, then every call to \texttt{class-slots} will
terminate.
\end{theorem}

Proof: Base case: If \texttt{class-slots} is called with an instance
of \texttt{standard-class}, then by definition of satiation, the call
will terminate.  If \texttt{class-slots} is called with some other
class, then calls are made to
\texttt{compute-applicable-methods-using-classes},
\texttt{compute-effective-method}, and
\texttt{compute-discriminating-function} in order to compute a new
discriminating function for \texttt{class-slots}.  But these functions
are satiated with respect to \texttt{standard-generic-function} and as
\texttt{class-slots} is a standard-generic-function, those calls
will terminate. 

\section{Implementing \texttt{slot-value} and \texttt{(setf slot-value)}}

For reasons of brevity, the following discussion is about the function
\texttt{slot-value}, but the case of \texttt{(setf slot-value)} is
entirely analogous. 

In \emph{the Art of the Metaobject Protocol (AMOP)}
\cite{Kiczales:1991:AMP:574212}, these functions are mentioned as
prime examples of issues of \emph{metastability}.  The scenario that
is cited is that \texttt{slot-value} of an instance calls
\texttt{class-slots} on the class of the instance, and
\texttt{class-slots} is an accessor which calls \texttt{slot-value}.
In the AMOP, the metastability problem is resolved by recognizing that
the recursion must eventually reach \texttt{standard-class}, so that
treating \texttt{standard-class} as a special case resolves the
problem.

However, the scenario cited above represents a simplification of the
real one.  The specification requires \texttt{slot-value} to call
\texttt{slot-value-using-class} with the instance, the class of the
instance, and an \emph{effective slot definition metaobject}.  In
order for \texttt{slot-value} to find the right effective slot
definition metaobject, it has to traverse the list of effective slot
definition metaobjects until one is found that has the \emph{name} of
the slot given as an argument.  To find the name of an effective slot
definition metaobject, \texttt{slot-value} has to call
\texttt{slot-definition-name} which is an accessor which calls
\texttt{slot-value} which is again a metastability issue.

However, in \sysname{}, as
\refSec{sec-generic-function-dispatch-accessor-methods} explains,
accessors in \sysname{} do not call \texttt{slot-value}, so the
scenario from the AMOP does not apply.  Furthermore, since the
accessors \texttt{class-slots} and \texttt{slot-definition-name} are
\emph{satiated}
\seesec{sec-object-system-dealing-with-metastability-issues} these
functions do not have to call \texttt{slot-location} for the base
case. 

The standard methods on \texttt{slot-value-using-class} call the
reader function \texttt{slot-definition-location} on the effective
slot definition and use that location to call
\texttt{standard-instance-access} on the instance.
